Another Cool Coin-Weighing Problem
My coauthor, Konstantin Knop, sent me a coin-weighing problem that is really good. Surprisingly, it is old: it first appeared in a Russian math journal, Kvant, in 1973.
Share:Puzzle. At a trial, 14 coins were presented as material evidence. The expert tested the coins and discovered that seven of them were fake, the rest were real, and he knew exactly which coins were fake and which were real. The court only knows that counterfeit coins weigh the same, real coins weigh the same, and fake ones are lighter than real ones. The expert wants to use not more than three weighings on a balance scales without weights to prove to the court that all the counterfeit coins he found are really fake, and the rest are real. Could he do it?
Joseph:
Let’s call the real coins R1 through R7, and let’s call the fake coins F1 through F7.
Weigh R1 against F1; R1 is heavier. Everyone now knows R1 is real and F1 is fake.
Weigh F1+R2+R3 against R1+F2+F3; F1+R2+R3 is heavier. Everyone now knows R1, R2, R3 are real and F1, F2, F3 are fake.
Weigh F1+F2+F3+R4+R5+R6+R7 against R1+R2+R3+F4+F5+F6+F7. That settles everything.
This can naturally be generalized to handle 2^n-1 real coins and 2^n-1 fake coins in n weighings. But the question is, is this the greatest number of coins you can handle, regardless of the number of weighings? My guess is, probably not.
29 August 2018, 11:47 pmJoseph:
Let’s call the real coins R1 through R7, and let’s call the fake coins F1 through F7.
Weigh R1 against F1; R1 is heavier. Everyone now knows R1 is real and F1 is fake.
Weigh F1+R2+R3 against R1+F2+F3; F1+R2+R3 is heavier. Everyone now knows R1, R2, R3 are real and F1, F2, F3 are fake.
Weigh F1+F2+F3+R4+R5+R6+R7 against R1+R2+R3+F4+F5+F6+F7. That settles it.
This can be generalized to handle 2^n-1 real coins and 2^n-1 fake coins in n weighings. But the question is, is that the greatest number of coins you can handle for any number of weighings? My guess is, probably not. There’s probably some surprises lurking here.
29 August 2018, 11:52 pmsanjay:
First Weighing.
Place 4R+3F in left and 3R+4F in right pan. Left pan must be heavier.
Second Weighing.
Remove 2R from left pan and 2F from right pan. This will lead 2R+3F in left and 3R+2F in right pan. Right pan must be heavier.
This proves 2R and 2F removed after first weighing are true.
Third Weighing.
Remove 3F from left and 3R from right pan and add now proven 2F in left and 2R in right pan. The pans must balance.
This will prove all 14 coins true, 7 real and 7 fake.
2 September 2018, 1:36 amPesto:
A variant: the expert can choose the ratio (in (0,1)) of the weight of the fake coins to the real ones (but the court doesn’t know the ratio). Then 3 weighings always suffice.
3 September 2018, 2:10 pm